package com.abel.day028;

/**
 * @author xiachao
 * @date 2019/3/1
 */
public class Solution {

    public ListNode FindKthToTail(ListNode head, int k) {
        int count = 0;
        ListNode begin = head;
        while(head!=null){
            head = head.next;
            if(count++ < k){
                continue;
            }
            begin = begin.next;
        }
        return count < k?null: begin;
    }

    public ListNode ReverseList(ListNode head) {
        ListNode cur = null;
        while(head!=null){
            ListNode n = new ListNode(head.val);
            head = head.next;
            n.next = cur;
            cur = n;
        }
        return cur;
    }

    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode n = new ListNode(-1);
        ListNode ret = n;

        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }

        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                n.next = new ListNode(list1.val);
                list1 = list1.next;
            }else{
                n.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            n = n.next;
        }
        if(list1 != null){
            n.next = list1;
        }else{
            n.next = list2;
        }
        return ret.next;
    }

    public ListNode Merge2(ListNode list1,ListNode list2) {

        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode node;
        if(list1.val < list2.val){
            node =  list1;
            node.next = Merge2(list1.next, list2);
        }else {
            node =  list2;
            node.next = Merge2(list1, list2.next);
        }
        return node;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node3;
        node3.next = node5;

        node2.next = node4;
        //node4.next = node5;
        ListNode n = new Solution().Merge2(node1, node2);
        while(n!=null){
            System.out.print(n.val+", ");
            n = n.next;
        }
    }

}
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
